//房屋偷盗
class Solution {
public:
    int rob(vector<int>& nums) 
    {
        //dp[i][0] 不偷第i间房屋
        //dp[i][1] 偷第i间房屋
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        if(nums.size()==2) return max(nums[0],nums[1]);
        vector<vector<int>>dp(nums.size(),vector<int>(2,0));
        dp[0][1]=nums[0];
        dp[1][0]=nums[0];
        dp[1][1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++)
        {
            dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
            dp[i][1]=max(dp[i-2][0],dp[i-2][1])+nums[i];
        }
        return max(dp[nums.size()-1][0],dp[nums.size()-1][1]);
    }
};
//回文子字符串的个数
class Solution {
public:
    int countSubstrings(string s) 
    {
        if(s.size()==0) return 0;
        //dp[i][j] 表示i到j之间是否为回文字符串
        //i==j 时 dp[i][j]=true
        //s[i]==s[j] && i+1==j 时 dp[i][j]=true;
        //s[i]==s[j] 时 dp[i][j]=dp[i+1][j-1]
        //所以i从大到小遍历 j从小到大遍历 但是j至少要和i一样大
        int n=s.size();
        vector<vector<bool>>dp(n,vector<bool>(n,false));
        int res=n;
        for(int i=0;i<n;i++) dp[i][i]=true;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i+1;j<n;j++)
            {
                if(s[i]!=s[j]) continue;

                if(s[i]==s[j] && i+1==j) 
                {
                    dp[i][j]=true;
                    res++;
                }
                else if (s[i]==s[j] && dp[i+1][j-1])
                {
                    dp[i][j]=true;
                    res++;
                }
            }
        }
        return res;
    }
};

//实现前缀树
struct TrieNode
{
    TrieNode()
        :_isEnd(false)
    {
        memset(_next,0,sizeof(_next));
    }
    bool _isEnd;
    TrieNode* _next[26];
};
class Trie {
public:
    /** Initialize your data structure here. */
    Trie() 
    {
        _root =new TrieNode();
    }   
    
    /** Inserts a word into the trie. */
    void insert(string word) 
    {
        TrieNode* cur=_root;
        for(int i=0;i<word.size();i++)
        {
            if(cur->_next[word[i]-'a']==nullptr)
            {
                cur->_next[word[i]-'a']=new TrieNode();
                cur=cur->_next[word[i]-'a'];
            }
            else
            {
                cur=cur->_next[word[i]-'a'];
            }
        }
        cur->_isEnd=true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) 
    {
        TrieNode* cur=_root;
        for(int i=0;i<word.size();i++)
        {
            if(cur->_next[word[i]-'a']==nullptr)
            {
                return false;
            }
            else
            {
                cur=cur->_next[word[i]-'a'];
            }
        }
        if(cur->_isEnd) return true;
        else return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) 
    {
        TrieNode* cur=_root;
        for(int i=0;i<prefix.size();i++)
        {
            if(cur->_next[prefix[i]-'a']==nullptr)
            {
                return false;
            }
            else
            {
                cur=cur->_next[prefix[i]-'a'];
            }
        }
        return true;
    }
private:
    TrieNode *_root;
};